package com.ztom.top100;

/**
 * 最短无序连续子数组
 * <p>
 * https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
 *
 * @author ZhangTao
 */
public class Code96FindUnsortedSubarray {

    /**
     * 从左往右, 找到最后一个比左侧最高点小的位置
     * 从右往左, 找到最后一个比右侧最低点大的位置
     * 两者之间的区间就是需要排序的部分
     *
     *                ./
     *           /\  /
     *    /\    /  \/
     *  ./  \/\/
     * /
     *
     *
     * @param nums
     * @return
     */
    public int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 从左往右遍历
        int lmax = Integer.MIN_VALUE, r = -1;
        // 从右往左遍历
        int rmin = Integer.MAX_VALUE, l = -1;

        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] < lmax) {
                r = i;
            } else {
                lmax = nums[i];
            }

            if (nums[n - i - 1] > rmin) {
                l = n - i - 1;
            } else {
                rmin = nums[n - i - 1];
            }
        }

        return r == -1 ? 0 : r - l + 1;
    }
}
